#include <iostream>

using namespace std;

const int N = 2e6 + 10;

bool st[N];
int primes[N], cnt;
int tr[N << 2][2], idx;
int s[N << 2];

void insert(int x)
{
	int p = 0;
	
	for (int i = 21; i >= 0; i -- )
	{
		int v = ((x >> i) & 1);
		
		if (!tr[p][v]) tr[p][v] = ++ idx;
		p = tr[p][v];
		s[p] ++ ;
	}
}

void init(int x)
{
	for (int i = 2; i <= x; i ++ )
	{
		if (!st[i]) 
		{
			primes[cnt ++ ] = i;
			insert(i);
		}
		
		for (int j = 0; primes[j] * i <= x; j ++ )
		{
			st[primes[j] * i] = true;
			if (i % primes[j] == 0) break; 	
		}
	}
}



int query(int x)
{
	int p = 0;
	int res = 0;
	
	for (int i = 21; i >= 0; i -- )
	{
		int v = ((x >> i) & 1);
		
		if (v)
		{
			res += s[tr[p][1]];
		}
		
		p = tr[p][0];
	}
	
	return res;
}

int main()
{
	init(N - 1);
	int T;
	cin >> T;
	
	while (T -- )
	{
		int x;
		cin >> x;
		cout << query(x) << endl;
	}
	
	return 0;
}